﻿#define _CRT_SECURE_NO_WARNINGS 1
/*
1469：似乎在梦中见过的样子
【题目描述】
原题来自：2014 年湖北省队互测 Week2
「Madoka，不要相信 QB！」伴随着 Homura 的失望地喊叫，
Madoka 与 QB 签订了契约。
这是 Modoka 的一个噩梦，也同时是上个轮回中所发生的事。
为了使这一次 Madoka 不再与 QB 签订契约，Homura 决定在
刚到学校的第一天就解决 QB。然而，QB 也是有许多替身的
（但在第八话中的剧情显示它也有可能是无限重生的），不过，
意志坚定的 Homura 是不会放弃的——她决定消灭所有可能是 QB 的东西。
现在，她已感受到附近的状态，并且把它转化为一个长度为
n 的字符串交给了学 OI 的你。
现在你从她的话中知道，所有形似于 A+B+A 的字串都是 QB 或它的替身，
且 ∣A∣≥k,∣B∣≥1（位置不同其他性质相同的子串算不同子串，位置相同但拆分
不同的子串算同一子串），然后你必须尽快告诉 Homura 这个答案——QB
以及它的替身的数量。
注：对于一个字符串 S，∣S∣ 表示 S 的长度。
【输入】
第一行一个字符串 S，第二行一个数 k。
【输出】
仅一行一个数 ans，表示 QB 以及它的替身的数量。
【输入样例】
aaaaa
1
【输出样例】
6
【提示】
样例输入2
abcabcabc
2
样例输出2
8
数据范围:
对于全部数据，1≤∣S∣≤1.5×10^4,1≤k≤100，且字符集为所有小写字母。

分析：
对测试样例：
aaaaa
1
设s="aaaaa"，
假设s[0]为qb的左耳，中间的身体至少为1个字符，则在s[2]及其
后面的字符中寻找另一只右耳。
则s[2], s[3], s[4]都可表示qb的右耳，此时有了3种情况。
s[1]为左耳时，同样的思路，s[3]，s[4]又是2种情况。
s[2]为左耳时,只有s[4]是右耳，因此是1种情况。
假设s[0]和s[1]都为qb的左耳，则s[2]和s[3]是qb的左耳。
但因为这个字符串在耳朵为1个字符的时候已经被查找，属于同位置
不同拆分的情况。
因此有6种情况。

本质上是字符串的前i (i>=k)个字符和后面的字符串进行匹配，匹配成功
就找到了一只qb。
可用kmp算法进行枚举，但我认为即使是bf也能做，但效率会特别低。

*/
//kmp算法，失败案例，这一题就别想着不修改原字符串了，老实该做啥就做啥
#include <iostream>
#include <cstring>
#include <string>
#define endl '\n'
using namespace std;
typedef unsigned long long ull;
string st;
int k;
int p[1501];
ull ans;

void kmp(int s) {
	for (int i = 1; i < st.size(); i++)
		p[i] = s;
	int j = s;
	for (int i = s + 1; i < st.size(); i++) {
		while (j > s && st[j] != st[i])
			j = p[j - 1];
		if (j >= 0)
			if (st[i] == st[j])
				p[i] = ++j;
	}
	j = s;
	for (int i = s + 2; i < st.size(); i++) {
		while (j > s && st[i] != st[j])
			j = p[j - 1];
		if (st[i] == st[j])
			j++;
		while ((j - s + 1) * 2 >= i - s + 1)
			j = p[j - 1];
		if (j - s + 1 >= k)
			++ans;
	}
}

int main() {
	ios::sync_with_stdio(0);
	//freopen("data//seq2.in", "r", stdin);
	cin >> st >> k;
	for (int i = 0; i < st.size(); i++)
		kmp(i);
	cout << ans;
	return 0;
}


